#!/usr/bin/python3

try:
    t = int(input())
    ret = []
    ids = 1
    while t > 0:
        n, m = input().split()
        i = 1
        j = 0
        n = int(n)
        m = int(m)
        while 1:
            i = i + m
            if i <= n:
                j = j + 1
            elif i % n != 1:
                i = i % n
                j = j + 1
            else:
                j = j + 1
                ret.append(f"Case #{ids}: {j}")
                break
        t = t - 1
        ids = ids + 1

    print("\n".join(ret))
except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
